#include <iostream>
#include <cstdlib>
#include <ctime>
#include <fstream>

using namespace std;

struct Node
{
    Node* left;
    Node* right;
    int key;
    int priority;
    int count;
    Node(int k = 0, int p = 0): key(k), priority(p), left(0), right(0), count(0){}
};

typedef Node* node_point;

struct decart_tree
{

public:
    decart_tree(): tree_root(0)
    {
        srand(time(NULL));
    }

    void insert(int key)
    {
        Node* new_node = new Node(key, rand());
        insert_node(tree_root, new_node);
    }

    int find_kthkey(int k)
    {
        return kthkey(tree_root, k);
    }

    void erase(int key)
    {
        if (tree_root == 0) return;
        erase_node(tree_root, key);
    }

    void print_tree()
    {
        print_node(tree_root, 0, "");
    }

protected:
    decart_tree(node_point p)
    {
        tree_root = p;
    }
    void merge(node_point& root, node_point l, node_point r)
    {
        if (!l || !r)
            root = l ? l : r;
        else if (l->priority > r->priority)
            merge(l->right, l->right, r), root = l;
        else
            merge(r->left, l, r->left), root = r;
        update_count(root);
    }

    int kthkey(node_point root, int k)
    {
        if (count(root->left) + 1 == k)
            return root->key;
        else if (k < count(root->left) + 1)
                return kthkey(root->left, k);
            else
                return kthkey(root->right, k - count(root->left) - 1);
    }

    void split(node_point root, int key, node_point& l, node_point& r)
    {
        if (!root)
            l = r =0;
        else
            if (key < root->key)
                split(root->left, key, l, root->left), r = root;
            else
                split(root->right, key, root->right, r), l = root;
        update_count(root);
    }

    void insert_node(node_point& root, node_point it)
    {
        if (!root)
            root = it;
        else if (it->priority > root->priority)
            split(root, it->key, it->left, it->right), root = it;
        else
            insert_node(it->key < root->key ? root->left : root->right, it);
        update_count(root);
    }

    void erase_node(node_point& root, int key)
    {
        if (root->key == key)
            merge(root, root->left, root->right);
        else
            erase_node(key < root->key ? root->left : root->right, key);
        update_count(root);
    }

    void print_node(node_point root, int depth, string s)
    {
        if (root)
        {
            for (int i = 0; i < depth; ++i) cout<<"  ";
            cout<<s<<' '<<root->key<<' '<<root->priority<<' '<<root->count<<endl;
            print_node(root->left, depth + 1, "l");
            print_node(root->right, depth + 1, "r");
        }
    }

    node_point tree_root;

    int count(node_point p)
    {
        return p == 0 ? 0 : p->count;
    }

    void update_count(node_point curr)
    {
        if (curr)
            curr->count = 1 + count(curr->left) + count(curr->right);
    }
};

int main()
{
    freopen("input.txt", "r", stdin);
    int n;
    cin>>n;
    decart_tree t;
    for (int i = 0; i < n ; ++i)
    {
        string s;
        cin>>s;
        if (s == "add")
        {
            int key;
            cin>>key;
            t.insert(key);
        } else if (s == "delete")
        {
            int key;
            cin>>key;
            t.erase(key);
        } else if (s == "print")
        {
            t.print_tree();
        } else if (s == "kthkey")
        {
            int key;
            cin>>key;
            int res = t.find_kthkey(key);
            cout<<res<<endl;
        }
    }
    return 0;
}
